import java.util.Arrays;

public class Solution924 {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        // 由 n 个节点组成的网络
        int n = graph.length;

        // 并查集 处理 连接
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }

        // 父节点 "染色"
        int[] count = new int[n];
        for (int node : initial) {
            int root = unionFind.find(node);
            count[root] += 1;
        }
        int res = -1;
        int maxSize = -1;
        for (int node : initial) {
            int root = unionFind.find(node);
            // 对于 initial 中每个颜色唯一的节点，都去计算联通分量的大小
            if (count[root] == 1) {
                int rootSize = unionFind.size[root];
                // 能够最小化 M(initial) 的节点 || 如果有多个节点满足条件，就返回索引最小的节点。
                if ((rootSize > maxSize) || (rootSize == maxSize && node < res)) {
                    maxSize = rootSize;
                    res = node;
                }
            }
        }

        // 如果 initial 中没有颜色唯一的节点，直接返回 min(initial)
        if (res == -1) {
            res = Integer.MAX_VALUE;
            for (int node : initial) {
                res = Math.min(res, node);
            }
        }
        return res;
    }

    private static class UnionFind {
        // 记录每个节点的父节点
        int[] parent;
        // 记录每棵树的重量
        int[] rank;
        // (可选) 连通分量
        int count;
        // 联通分量大小
        int[] size;

        // 0 ~ n-1
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = i;
            }
            count = n;
            // 联通分量大小
            size = new int[n];
            Arrays.fill(size, 1);
        }

        // 返回节点 x 的根节点
        private int find(int x) {
            int ret = x;
            while (ret != parent[ret]) {
                // 路径压缩
                parent[ret] = parent[parent[ret]];
                ret = parent[ret];
            }
            return ret;
        }

        // 将 p 和 q 连通
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                if (rank[rootP] > rank[rootQ]) {
                    parent[rootQ] = rootP;
                    size[rootP] += size[rootQ];
                } else if (rank[rootP] < rank[rootQ]) {
                    parent[rootP] = rootQ;
                    size[rootQ] += size[rootP];
                } else {
                    parent[rootQ] = rootP;
                    size[rootP] += size[rootQ];
                    // 重量平衡
                    rank[rootP] += 1;
                }
                count--;
            }
        }

        // p 和 q 是否连通
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
    }
}
/*
924. 尽量减少恶意软件的传播
https://leetcode.cn/problems/minimize-malware-spread/

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
提示：
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial 中所有整数均不重复

并查集。
case1: 对于 initial 中颜色唯一的节点，找联通分量 size 最大的。
case2: 如果 initial 中的两个节点属于相同的联通分量，那么即使移除了也是不会减少 M(initial) 的，返回索引最小的节点即可。
注意 UnionFind 中 int[] size; 的处理
时间复杂度 O(n^2)
空间复杂度 O(n)
相似题目: 928. 尽量减少恶意软件的传播 II
https://leetcode.cn/problems/minimize-malware-spread-ii/
 */